package com.yyf.test2;

import javax.swing.tree.TreeNode;
import java.util.*;

public class toCamelCase {
    public static String toCamelCase(String input) {
        if (input == null) return null;
        String[] StringChar = input.split("-");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < StringChar.length; i++) {
            String firstString = StringChar[0];
            if (firstString.isEmpty()) {
                continue;
            }
            if (i == 0) {
                sb.append(firstString);
            } else {
                sb.append(Character.toUpperCase(firstString.charAt(0))).append(firstString.substring(1));
            }
        }

        return sb.toString();
    }

    public int longestConsecutive(int[] nums) {
        if (nums == null && nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        int MaxSize = 0;
        for (int num : nums) {
            set.add(num);
        }
        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int curnum = num;
                int curSize = 1;
                while (set.contains(curnum + 1)) {
                    curnum++;
                    curSize++;
                }
                MaxSize = Math.max(curSize, MaxSize);
            }

        }
        return MaxSize;
    }


    public void moveZeroes(int[] nums) {
        int zeroIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[zeroIndex] = nums[i];
                zeroIndex++;
            }
        }
        for (int i = zeroIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }


    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0;
        int max = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            while (set.contains(c)) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(c);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //不修改原链表
    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode newword = new ListNode(cur.val);
            newword.next = pre;
            pre = newword;
            cur = cur.next;
        }
        return pre;
    }

    //反转一整个
    public boolean isPalindrome(ListNode head) {
        ListNode head2 = rerverListNode(head);
        while (head != null && head2 != null) {
            if (head.val != head2.val) return false;
            head = head.next;
            head2 = head2.next;
        }

        return true;
    }

    //快慢指针
    public boolean isPalindrome2(ListNode head) {
        ListNode p1 = head;
        ListNode p3 = head;
        while (p1 != null && p1.next != null) {
            p1 = p1.next.next;
            p3 = p3.next;
        }
        ListNode p2 = rerverListNode(p3);
        boolean result = true;
        while (p2 != null && result) {
            if (head.val != p2.val) return false;
            head = head.next;
            p2 = p2.next;
        }
        return result;
    }

    private ListNode rerverListNode(ListNode list) {
        ListNode pre = null;
        ListNode cur = list;
        while (cur != null) {
            ListNode newword = new ListNode(cur.val);
            newword.next = pre;
            pre = newword;
            cur = cur.next;
        }
        return pre;
    }


    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        doall(root, list);
        return list;


    }

    private void doall(TreeNode root, List list) {
        if (root == null) return;
        doall(root.left, list);
        list.add(root.val);
        doall(root.right, list);
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return left > right ? left + 1 : right + 1;
    }


    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode newroot = root.left;
        root.left = root.right;
        root.right = newroot;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }


    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        return (left.val == right.val)
                && isMirror(left.left, right.right)
                && isMirror(left.right, right.left);
    }


    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null)return 0;
        int left=diameterOfBinaryTree(root.left);
        int right=diameterOfBinaryTree(root.right);
        int rootleft=MaxPath(root.left);
        int rootright=MaxPath(root.right);
        int curPath=rootleft+rootright;
        return Math.max(left,Math.max(right,curPath));
    }
    private int MaxPath(TreeNode root){
        if(root==null) return 0;
        int left=MaxPath(root.left);
        int right=MaxPath(root.right);
        return Math.max(left,right)+1;
    }
//少一次递归
    int MaxPath=0;
    public int diameterOfBinaryTree2(TreeNode root) {
        MaxPathToTree(root);
        return MaxPath;
    }
    private int MaxPathToTree(TreeNode root){
        if(root==null)return 0;
        int left=MaxPathToTree(root.left);
        int right=MaxPathToTree(root.right);
        MaxPath=Math.max(MaxPath,left+right);
        return Math.max(right,left)+1;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return  sortedArrayToBST(nums,0,nums.length - 1);
    }
    private TreeNode sortedArrayToBST(int[] nums,int left,int right){
        if(left>right) return null;
        int mid=(right+left)/2;
        TreeNode root1=new TreeNode(nums[mid]);
        root1.left=sortedArrayToBST(nums,left,mid-1);
        root1.right=sortedArrayToBST(nums,mid+1,right);
        return root1;
    }
//有效的括号
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){return mid;
            }else  if(nums[mid]<target){
                left=mid+1;
            }else right=mid-1;
        }
        return left;
    }
//有效的括号
    public boolean isValid(String s) {
        Deque<Character> stack=new ArrayDeque<>();
        for(char c:s.toCharArray()){
            if(c == '('||c == '['||c == '{'){
                stack.push(c);
            }else{
                if(stack.isEmpty())return false;
                char curchar=stack.pop();
                if(
                        c==')'&&curchar!='('||
                                c=='}'&&curchar!='{'||
                                c==']'&&curchar!='['
                )return false;
            }
        }
        return stack.isEmpty();
    }
//买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int profit=0;
        int minprice=prices[0];
        for(int i=0;i<prices.length;i++){
            int price=prices[i];
            profit=Math.max(profit,price-minprice);
            minprice=Math.min(minprice,price);
        }
        return profit;
    }
//只出现一次的数字
    public int singleNumber(int[] nums) {
        int result =0;
        for(int num:nums){
            result^=num;
        }
        return result;
    }
//爬楼梯
    public int climbStairs(int n) {
        int[] all=new int[n+1];
        all[0]=1;
        all[1]=1;
        for(int i=2;i<=n;i++){
            all[i]=all[i-1]+all[i-2];
        }
        return all[n];
    }
//杨辉三角
    public List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> list1=new ArrayList<>();
        for(int i=0;i<numRows;i++){
            ArrayList<Integer> list2=new ArrayList<>();
            for(int j=0;j<=i;j++){
                if(j==0||j==i){
                    list2.add(1);
                }else
                {
                    list2.add(list1.get(i-1).get(j-1)+list1.get(i-1).get(j));
                }

            }
            list1.add(list2);
        }
        return list1;
    }

//多数元素
    public int majorityElement(int[] nums) {
        int count=0;
        int curnum=0;
        for(int num:nums){
            if(count==0){
                curnum=num;
            }
            count+=curnum==num?1:-1;
        }
        return curnum;
    }
//盛最多水的容器
    public int maxArea(int[] height) {
        int left=0;
        int right=height.length-1;
        int maxarea=0;
        while(left<right){
            int curarea=Math.min(height[left],height[right])*(right-left);
            maxarea=Math.max(maxarea,curarea);
            if(height[left]<height[right]){
                left++;
            }else{
                right--;
            }
        }
        return maxarea;
    }
    //三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        if(nums==null||nums.length<3)return list;
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=0;i<n-2;i++){
            if(i>0&&nums[i]==nums[i-1])continue;
            int left=i+1;
            int right=n-1;
            while(left<right){
                int sum=nums[i]+nums[right]+nums[left];
                if(sum==0){
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left<right&&nums[left]==nums[left+1]){left++;}
                    while(left<right&&nums[right]==nums[right-1]){right--;}
                    left++;
                    right--;
                }else if(sum<0){
                    left++;

                }else{
                    right--;
                }

            }
        }
        return list;
    }
}

